#define MAX_CHARS 256
#define MAX_ESCOPOS 256

struct escopo {
	char caracteres[MAX_CHARS];
	int caractereAtual;
};

struct escopo escopos[MAX_ESCOPOS];
int escopoAtual = 0;
int debug = 1;

void novo_escopo() {
	escopoAtual++;
	escopos[escopoAtual].caractereAtual = 0;
	if (debug == 1) {printf("Novo escopo nivel %d\n", escopoAtual);imprime();}
}

void entra(char entrada) {
	int atual = escopos[escopoAtual].caractereAtual;
	escopos[escopoAtual].caracteres[atual] = entrada;
	escopos[escopoAtual].caractereAtual++;
	if (debug == 1) {printf("Caractere adicionado %c\n", entrada);imprime();}
}

void tenta_reduzir() {
	int naoTerminou = 1;
	
	while (naoTerminou) {
		naoTerminou = 0;
		int posicaoCaracter = 0;
		
		while (posicaoCaracter <= escopos[escopoAtual].caractereAtual) {
			
			if (escopos[escopoAtual].caracteres[posicaoCaracter] == 'S' || escopos[escopoAtual].caracteres[posicaoCaracter] == 's') {
				if(posicaoCaracter + 4 <= escopos[escopoAtual].caractereAtual) {
					char xis = escopos[escopoAtual].caracteres[posicaoCaracter + 1];
					char ypsilon = escopos[escopoAtual].caracteres[posicaoCaracter + 2];
					char ze = escopos[escopoAtual].caracteres[posicaoCaracter + 3];
					novo_escopo();
					novo_escopo();
					entra(xis);
					entra(ze);
					tenta_reduzir();
					fecha_escopo();
					novo_escopo();
					entra(xis);
					entra(ypsilon);
					tenta_reduzir();
					fecha_escopo();
					int posicaoTemp = posicaoCaracter;
					int numCopias = escopos[escopoAtual].caractereAtual;
					int posicaoAFechar = 0;
					while (posicaoAFechar < escopos[escopoAtual].caractereAtual) {
						escopos[escopoAtual - 1].caracteres[posicaoTemp] = escopos[escopoAtual].caracteres[posicaoAFechar];
						escopos[escopoAtual].caracteres[posicaoAFechar] = '\0';
						posicaoAFechar++;
						posicaoTemp++;
					}
					escopos[escopoAtual].caractereAtual = 0;
					escopoAtual--;
					
					while (posicaoTemp < escopos[escopoAtual].caractereAtual - numCopias) {
						escopos[escopoAtual].caracteres[posicaoTemp] = escopos[escopoAtual].caracteres[posicaoTemp + numCopias];
						posicaoTemp++;
					}
					naoTerminou = 1;
					if (debug == 1) {printf("Reduziu S\n", escopoAtual);imprime();}
				}
			}
			else if (escopos[escopoAtual].caracteres[posicaoCaracter] == 'K' || escopos[escopoAtual].caracteres[posicaoCaracter] == 'K') {
				if(posicaoCaracter + 3 <= escopos[escopoAtual].caractereAtual) {
					int posicaoTemp = posicaoCaracter;
					escopos[escopoAtual].caracteres[posicaoTemp] = escopos[escopoAtual].caracteres[posicaoTemp + 1];
					posicaoTemp++;
					while (posicaoTemp < escopos[escopoAtual].caractereAtual - 2) {
						escopos[escopoAtual].caracteres[posicaoTemp] = escopos[escopoAtual].caracteres[posicaoTemp + 2];
						posicaoTemp++;
					}
					escopos[escopoAtual].caractereAtual--;
					escopos[escopoAtual].caracteres[escopos[escopoAtual].caractereAtual] = '\0';
					escopos[escopoAtual].caractereAtual--;
					escopos[escopoAtual].caracteres[escopos[escopoAtual].caractereAtual] = '\0';
					naoTerminou = 1;
					if (debug == 1) {printf("Reduziu K\n", escopoAtual);imprime();}
				}
			}
			else if (escopos[escopoAtual].caracteres[posicaoCaracter] == 'I') {
				if(posicaoCaracter + 2 <= escopos[escopoAtual].caractereAtual) {
					int posicaoTemp = posicaoCaracter;
					while (posicaoTemp < escopos[escopoAtual].caractereAtual - 1) {
						escopos[escopoAtual].caracteres[posicaoTemp] = escopos[escopoAtual].caracteres[posicaoTemp + 1];
						posicaoTemp++;
					}
					escopos[escopoAtual].caractereAtual--;
					escopos[escopoAtual].caracteres[escopos[escopoAtual].caractereAtual] = '\0';
					naoTerminou = 1;
					if (debug == 1) {printf("Reduziu I\n", escopoAtual);imprime();}
				}
			}
			posicaoCaracter++;
		}
	}
}

void fecha_escopo() {
	int posicaoAFechar = 0;
	while (posicaoAFechar < escopos[escopoAtual].caractereAtual) {
		int posicaoAVoltar = escopos[escopoAtual - 1].caractereAtual;
		escopos[escopoAtual - 1].caracteres[posicaoAVoltar] = escopos[escopoAtual].caracteres[posicaoAFechar];
		escopos[escopoAtual].caracteres[posicaoAFechar] = '\0';
		escopos[escopoAtual - 1].caractereAtual++;
		posicaoAFechar++;
	}
	escopos[escopoAtual].caractereAtual = 0;
	escopoAtual--;
	if (debug == 1) {printf("Escopo nivel %d fechado\n", escopoAtual + 1);imprime();}
}

void imprime() {
	printf("%s\n",escopos[escopoAtual].caracteres);
}

int main(void) {
	entra('I');
	tenta_reduzir();
	novo_escopo();
	entra('K');
	tenta_reduzir();
	entra('K');
	tenta_reduzir();
	entra('I');
	tenta_reduzir();
	fecha_escopo();
	tenta_reduzir();
	novo_escopo();
	entra('I');
	tenta_reduzir();
	entra('I');
	tenta_reduzir();
	entra('K');
	tenta_reduzir();
	entra('S');
	tenta_reduzir();
	entra('I');
	tenta_reduzir();
	fecha_escopo();
	tenta_reduzir();

	imprime();
	return 0;
}
